Trees

> module Tree (Tree(..), forest, width, fold, rev) where

> import Aux
> import Data.List

> data Tree a = Lf a | Br [Tree a] deriving (Show,Eq)

> instance Functor Tree where
>   fmap f (Lf x) = Lf $! f x
>   fmap f (Br x) = Br $! map' (fmap f) x

> fold :: a -> (a -> a -> a) -> Tree a -> a
> fold z f (Lf c) = c
> fold z f (Br []) = z
> fold z f (Br b) = foldl1' f (map' (fold z f) b)

> forest :: Tree a -> [Tree a]
> forest (Lf x) = [Lf $! x]
> forest (Br x) = x

> rev :: Tree a -> Tree a
> rev (Br b) = Br $! reverse b
> rev x = x

> width :: Tree t -> Int
> width (Lf _) = 1
> width (Br b) = length b

> len :: Tree t -> [Int]
> len (Lf c) = []
> len (Br []) = []
> len (Br b) = length b !: foldl1' (zipKeep max) (map' len b)
